#define _CRT_SECURE_NO_WARNINGS

#include "Sort.h"
void Swap(int* x, int* y) {
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
void InsertSort(int* arr, int n) {
	for (int i = 0; i < n - 1; i++) {
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0) {
			if (arr[end] > tmp) {
				arr[end + 1] = arr[end];
				end--;
			}
			else break;
		}
		arr[end + 1] = tmp;
	}
}

void ShellSort(int* arr, int n) {
	int gap = n;
	while (gap > 1) {
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++) {
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0) {
				if (arr[end] > tmp) {
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else break;
			}
			arr[end + gap] = tmp;
		}
	}
}

void SelectSort(int* arr, int n) {
	int begin = 0, end = n - 1;
	while (begin < end) {
		int mini = begin, maxi = begin;
		for (int i = begin + 1; i <= end; i++) {
			if (arr[i] < arr[mini])mini = i; 
			if (arr[i] > arr[maxi])maxi = i;
		}
		if (maxi == begin)maxi = mini;
		Swap(&arr[mini], &arr[begin]);
		Swap(&arr[maxi], &arr[end]);
		begin++;
		end--;
	}
}

int QSort(int* arr, int left, int right) {
	int keyi = left++;
	while (left <= right) {
		while (left <= right && arr[right] > arr[keyi])--right;
		while (left <= right && arr[left] < arr[keyi])++left;
		if (left <= right) Swap(&arr[left++], &arr[right--]);
		
	}
	Swap(&arr[keyi], &arr[right]);
	return right;
}

int Hole(int* arr, int left, int right) {
	int key = arr[left];
	while (left < right) {
		while (left < right && arr[right] > key)--right;
		arr[left++] = arr[right];
		while (left < right && arr[left] < key)++left;
		arr[right--] = arr[left];
	}
	arr[left] = key;
	return left;
}
int lomuto(int* arr, int left, int right) {
	int prev = left, cur = prev + 1;
	while (cur <= right) {
		if (arr[cur] < arr[left] && ++prev != cur)
			Swap(&arr[prev], &arr[cur]);
		cur++;
	}
	Swap(&arr[left], &arr[prev]);
	return prev;
}
void QuickSort(int* arr, int left, int right) {
	if (left >= right) return;
	int keyi = lomuto(arr, left, right);
	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi + 1, right);
}

void QuickSortNonR(int* arr, int left, int right) {
	St box;
	STInit(&box);
	STPush(&box, right);
	STPush(&box, left);
	while (!STEmpty(&box)) {
		left = STTop(&box);
		STPop(&box);
		right = STTop(&box);
		if (left >= right) continue;
		STPop(&box);
		int key = left, cur = key + 1;
		while (cur <= right) {
			if (arr[cur] < arr[left] && ++key != cur)
				Swap(&arr[key], &arr[cur]);
			cur++;
		}
		Swap(&arr[left], &arr[key]);
		STPush(&box, key - 1);
		STPush(&box, left);
		STPush(&box, right);
		STPush(&box, key + 1);
	}
	STDestroy(&box);
}

void Merge(int* arr, int left, int right, int* tmp) {
	if (left >= right) return;
	int mid = (left + right) / 2;
	Merge(arr, left, mid, tmp);
	Merge(arr, mid + 1, right, tmp);
	int b1 = left, e1 = mid, b2 = mid + 1, e2 = right, l = 0;
	while (b1 <= e1 && b2 <= e2)tmp[l++] = (arr[b1] < arr[b2]) ? arr[b1++] : arr[b2++];
	while (b1 <= e1)tmp[l++] = arr[b1++];
	while (b2 <= e2)tmp[l++] = arr[b2++];
	for (int i = 0; i < l; i++)arr[left + i] = tmp[i];
}

void MergeSort(int* arr, int n) {
	int* tmp = (int*)malloc(n * sizeof(int));
	Merge(arr, 0, n - 1, tmp);
	free(tmp);
}
void CountSort(int* arr, int n) {
	if (n <= 1)return;
	int min = arr[0], max = arr[0], i = 0, sz = 0;
	for (i = 1; i < n; i++) {
		if (arr[i] < min)min = arr[i];
		if (arr[i] > max)max = arr[i];
	}
	int* count = (int*)malloc((max - min + 1) * sizeof(int));
	if (count == NULL)return;
	for (i = 0; i < max - min + 1; i++)count[i] = 0;
	for (i = 0; i < n; i++)count[arr[i] - min]++;
	for (i = 0; i < max - min + 1; i++)while (count[i]--)arr[sz++] = i + min;
	free(count);
}